package com.base.recursion;

import java.util.*;

/**
 * 282. 给表达式添加运算符
 *
 * 给定一个仅包含数字0-9的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、-或*，返回所有能够得到目标值的表达式。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/expression-add-operators
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author leon
 * @date 2021年10月16日 18:27
 */
public class AddOperators {
        int n;
        String num;
        int target;
        List<String> ans;

        public List<String> addOperators(String num, int target) {
            this.n = num.length();
            this.num = num;
            this.target = target;
            this.ans = new ArrayList<String>();
            StringBuffer expr = new StringBuffer();
            backtrack(expr, 0, 0, 0);
            return ans;
        }

        public void backtrack(StringBuffer expr, int i, long res, long mul) {
            if (i == n) {
                if (res == target) {
                    ans.add(expr.toString());
                }
                return;
            }
            int signIndex = expr.length();
            if (i > 0) {
                expr.append(0); // 占位，下面填充符号
            }
            long val = 0;
            // 枚举截取的数字长度（取多少位），注意数字可以是单个 0 但不能有前导零
            for (int j = i; j < n && (j == i || num.charAt(i) != '0'); ++j) {
                val = val * 10 + num.charAt(j) - '0';
                expr.append(num.charAt(j));
                if (i == 0) { // 表达式开头不能添加符号
                    backtrack(expr, j + 1, val, val);
                } else { // 枚举符号
                    expr.setCharAt(signIndex, '+');
                    backtrack(expr, j + 1, res + val, val);
                    expr.setCharAt(signIndex, '-');
                    backtrack(expr, j + 1, res - val, -val);
                    expr.setCharAt(signIndex, '*');
                    backtrack(expr, j + 1, res - mul + mul * val, mul * val);
                }
            }
            expr.setLength(signIndex);
        }

}
